package org.hawk.gwt.ppc.utils;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.RandomAccess;
import java.util.Set;
/**
 * This collection ensures that elements are unique and provides list-based random access
 * for each element (O(1)), fast add and get index operations. However it takes more memory than e.g.
 * basic map implementations. This implementation also do not guaranty that particular add or remove 
 * operation will be fast since its backed by hashtable and array that can have some delays for rebuilding 
 * the base data structure.
 * 
 * This implementation is not a thread safe. It provides fall-fast behavior as e.g. java.utils.HashMap.
 * 
 * @author alex.bereznevatiy@gmail.com
 *
 * @param <E>
 */
public class UniqueList<E> extends AbstractList<E> implements Set<E>, List<E>, RandomAccess {
	
	private Map<E, Integer> map;
	private List<E> list;
	
	public UniqueList() {
		this(10);
	}
	
	public UniqueList(int defaultSize) {
		if (defaultSize < 0) {
			throw new IllegalArgumentException("Capasity is " + defaultSize);
		}
		map = new HashMap<E, Integer>(defaultSize);
		list = new ArrayList<E>(defaultSize);
	}

	@Override
	public E get(int index) {
		return list.get(index);
	}

	@Override
	public int size() {
		return list.size();
	}

	@Override
	public E set(int index, E element) {
		if (map.containsKey(element) && !map.get(element).equals(index)) {
			return null;
		}
		map.put(element, index);
		return list.set(index, element);
	}

	@Override
	public void add(int index, E element) {
		if (map.containsKey(element)) {
			return;
		}
		map.put(element, index);
		list.add(index, element);
	}
	
	public boolean add(E e) {
		if (map.containsKey(e)) {
			return false;
		}
		map.put(e, list.size());
		list.add(e);
		return true;
    }

	@Override
	public E remove(int index) {
		E el = list.remove(index);
		map.remove(el);
		return el;
	}

	@Override
	public int indexOf(Object o) {
		Integer index = map.get(o);
		return index == null ? -1 : index.intValue();
	}

	@Override
	public int lastIndexOf(Object o) {
		return indexOf(o);
	}

	@Override
	public void clear() {
		map.clear();
		list.clear();
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		boolean modified = false;
		Iterator<? extends E> e = c.iterator();
		while (e.hasNext()) {
			E element = e.next();
			if (map.containsKey(element)) {
				continue;
			}
			map.put(element, index);
			list.add(index++, element);
		    modified = true;
		}
		return modified;
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		if (fromIndex < 0 || toIndex > size() || fromIndex > toIndex) {
			throw new IndexOutOfBoundsException("Sublist(" + fromIndex + ", " + toIndex + ") is out of list range.");
		}
		UniqueList<E> result = new UniqueList<E>(toIndex - fromIndex);
		ListIterator<E> iterator = listIterator(fromIndex);
		while (iterator.hasNext() && iterator.nextIndex() < toIndex) {
			result.add(iterator.next());
		}
		return result;
	}

	@Override
	public boolean isEmpty() {
		return list.isEmpty();
	}

	@Override
	public boolean contains(Object o) {
		return map.containsKey(o);
	}

	@Override
	public boolean remove(Object o) {
		Integer index = map.remove(o);
		if (index == null) {
			return false;
		}
		list.remove(index);
		return true;
	}
}
